#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
        int n, m, s;
        cin >> n >> m >> s;

        vector<vector<vector<int>>> gh(n + 1);
        for(int i = 0, u, v, w; i < m; i++){
                cin >> u >> v >> w;
                gh[u].push_back({v, w});
        }

        vector<int> dist(n + 1, INT32_MAX);
        vector<int> vis(n + 1, 0);
        auto cmp = [](auto a, auto b) { return a[1] > b[1]; };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);

        pq.push({s, 0});
        dist[s] = 0;

        while(!pq.empty()){
                auto e = pq.top();
                pq.pop();
                int u = e[0];
                if(vis[u]){
                        continue;
                }

                vis[u] = 1;
                for(auto e : gh[u]){
                        int v = e[0], w = e[1];
                        if(!vis[v] && dist[u] + w < dist[v]){
                                dist[v] = dist[u] + w;
                                pq.push({v, dist[v]});
                        }        
                }
        }

        for(int i = 1;i <= n; i++){
                cout << dist[i] << ' ';
        }
        cout << endl;

        return 0;
}
